package com.lw.leetcode.dp.b;

/**
 * dp
 * 375. 猜数字大小 II
 *
 * @Author liw
 * @Date 2021/8/28 23:06
 * @Version 1.0
 */
public class GetMoneyAmount {

    public static void main(String[] args) {
        GetMoneyAmount test = new GetMoneyAmount();

        // 16
//        int n = 10;

        // 49
//        int n = 20;

        // 400
        int n = 100;

        // 952
//        int n = 200;

        int moneyAmount = test.getMoneyAmount(n);
        System.out.println(moneyAmount);
    }

    public int getMoneyAmount(int n) {
        int[][] arr = new int[n][n];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                int min = Math.min(i + 1 + arr[i + 1][j], j + 1 + arr[i][j - 1]);
                for (int k = i + 1; k < j; k++) {
                    int max = k + 1 + Math.max(arr[i][k - 1], arr[k + 1][j]);
                    min = Math.min(min, max);
                }
                arr[i][j] = min;
            }
        }
        return arr[0][n - 1];
    }

}
